package dp;

import java.util.Arrays;

/**
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 *
 * 已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，
 * 从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 *
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。
 * 如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 *
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 *
 */
public class leetCode887_superEggDrop {

    // dp[i][j] 一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少实验的次数
    // 注意：
    // 1、i 表示的是楼层的大小，不是第几层的意思，例如楼层区间 [8, 9, 10] 的大小为 3，
    // 这一点是在状态转移的过程中调整的定义
    
    // 2、j 表示可以使用的鸡蛋的个数，它是约束条件，我个人习惯放在后面的维度，表示消除后效性的意思

    public static int superEggDrop(int K, int N) {

        int[][] dp = new int[N + 1][K + 1];

        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        // i = 0，表示楼层个数为0，无论多少个鸡蛋，结果都是0
        // i = 1, 表示楼层个数为1，无论多少个鸡蛋，除了鸡蛋为0的时候，结果都是1,
        for (int i = 0; i < K + 1; i++) {
            dp[0][i] = 0;
            dp[1][i] = 1;
        }
        // 鸡蛋为0，楼层为1的情况要重新赋值一下；
        dp[1][0] = 0;

        // j = 0,表示0个鸡蛋，那无论几层楼，次数就是0次
        // i = 1,表示1个鸡蛋，那无论几层楼，次都都是楼层个数
        for (int i = 0; i < N + 1; i++) {
            dp[i][0] = 0;
            dp[i][1] = i;
        }

        return 0;
    }

    public static void main(String[] args) {
        int i = superEggDrop(5, 10);

        System.out.println(1);
    }
}
